\begin{frame}
\frametitle{Rosenfeld grammars}

Another idea of creating 2d languages with grammars has been developed by Rosenfeld where
\begin{itemize}
	\item We start with an infinite layer containing the start symbol and the rest is all blank symbols
	\item Derivation proceeds as follows, that we have rules $A \rightarrow B$ with A and B are pictures of the same size. A rule can be applied to an image, if the pattern of A can be located within the image. The derivation is to replace this subpicture by B. 
	\item It is necesary, that for each rule $A \rightarrow B$, A and B must contain at least one non blank symbol. 
\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Isometric array grammars}

\begin{define}[IAG \cite{rosenfeldpicture}]
$G = (V, V_T, \Pi, S, \#)$ is called an isometric array grammar where

\begin{itemize}
	\item V is a non-empy finite set of symbols, the vocabulary
	\item $V_T$ is a non-empty finite set of terminal symbols ($V_T \subsetneq V$)
	\item $\Pi$ contains the production rules, where for any rule $A \rightarrow B$: $l_1(A) = l_1(B)$ and $l_2(A) = l_2(B)$ and A and B containts at least one non blank symbol. 
	\item S the start symbol
	\item $\#$ is the blank symbol
\end{itemize}

\end{define}

\end{frame}

\begin{frame}
\frametitle{Example}
\begin{Example}
$G = (V, V_T, \Pi, S, \#)$ where
\begin{itemize}
	\item $V = \{S, H, V, a, \#\}$
	\item $V_T = \{a\}$
	\item $\Pi$ contain the rules: 
	\begin{columns}
	\begin{column}[l]{5cm}
		\begin{itemize}
			\item $S\# \rightarrow aS$
			\item 
		$\begin{matrix}
			S & \# & \# \\[-0.5ex]
			 & \# &
		\end{matrix} 
		\rightarrow
		\begin{matrix}
			a & a & H \\[-0.5ex]
			 & V &
		\end{matrix}$
		\end{itemize}
	\end{column}
	\begin{column}[c]{2.5cm}
		\begin{itemize}
			\item $H\# \rightarrow aH$
			\item $H \rightarrow a$
		\end{itemize}
	\end{column}
	\begin{column}[r]{2.5cm}
		\begin{itemize}
			\item 
		$\begin{matrix}
			V \\[-0.5ex]
			\#	
		\end{matrix} 
		\rightarrow
		\begin{matrix}
			a \\[-0.5ex]
			V	
		\end{matrix}
		$
			\item $V \rightarrow a$
		\end{itemize}
	\end{column}
	\end{columns}
\end{itemize}
\end{Example}

This grammar creates the language, which contains t-shaped structures of a's. 

\end{frame}

\begin{frame}
\frametitle{Example derivation}

\[
\begin{aligned}
\begin{matrix}
\# & \# & \# & \# & \# \\[-0.5ex]
\# & S & \# & \# & \# \\[-0.5ex]
\# & \# & \# & \# & \# \\[-0.5ex]
\# & \# & \# & \# & \# \\[-0.5ex]
\# & \# & \# & \# & \# 
\end{matrix}
\end{aligned}
\Rightarrow
\begin{aligned}
\begin{matrix}
\# & \# & \# & \# & \# \\[-0.5ex]
\# & a & a & H & \# \\[-0.5ex]
\# & \# & V & \# & \# \\[-0.5ex]
\# & \# & \# & \# & \# \\[-0.5ex]
\# & \# & \# & \# & \# 
\end{matrix}
\end{aligned}
\Rightarrow
\begin{aligned}
\begin{matrix}
\# & \# & \# & \# & \# \\[-0.5ex]
\# & a & a & a & \# \\[-0.5ex]
\# & \# & V & \# & \# \\[-0.5ex]
\# & \# & \# & \# & \# \\[-0.5ex]
\# & \# & \# & \# & \# 
\end{matrix}
\end{aligned}
\]

\[
\Rightarrow
\begin{aligned}
\begin{matrix}
\# & \# & \# & \# & \# \\[-0.5ex]
\# & a & a & a & \# \\[-0.5ex]
\# & \# & a & \# & \# \\[-0.5ex]
\# & \# & V & \# & \# \\[-0.5ex]
\# & \# & \# & \# & \# 
\end{matrix}
\end{aligned}
\Rightarrow
\begin{aligned}
\begin{matrix}
\# & \# & \# & \# & \# \\[-0.5ex]
\# & a & a & a & \# \\[-0.5ex]
\# & \# & a & \# & \# \\[-0.5ex]
\# & \# & a & \# & \# \\[-0.5ex]
\# & \# & \# & \# & \# 
\end{matrix}
\end{aligned}
\]
\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Subclasses of IAG}

With restricting the form of production rules ($A \rightarrow B$), there can be achieved a chomsky like hierachy. 

\begin{define}
If non-$\#$ symbols in A are not rewriten by $\#$'s, G is called monotonic array grammar (MAG). 
\end{define}

\begin{define}
If A consists of exactly one nonterminal (there can be $\#$'s too), G is called a context free array grammar (CFAG). 
\end{define}

\begin{define}
If A consists of one non-terminal (and possibly one $\#$-symbol), and B contains exactly one terminal and zero or one nonterminal, then G is called regular array grammar. 
\end{define}

\begin{thm}
\[RAL \subsetneq CFAL \subsetneq MAL \subsetneq IAL\]
\end{thm}

\end{frame}